package com.zhanghp.class035;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * 最大频率栈<br/>
 * 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/
 *
 * @author zhanghp
 * @since 2024/4/16 11:48
 */
public class Code06_MaximumFrequencyStack {

    static class FreqStack {

        /**
         *  每层节点<br/>
         */
        public Map<Integer, ArrayList<Integer>> cntValues;

        /**
         * 每一个数出现了几次
         */
        public Map<Integer, Integer> valueTimes;

        /**
         * 最大次数
         */
        public int topicTimes;

        public FreqStack() {
            cntValues = new HashMap<>();
            valueTimes = new HashMap<>();
            topicTimes = 0;
        }

        public void push(int val) {
            // 1. 获取val出现的次数，（若未出现，则默认1，用来接下来的处理操作）
            Integer valTimes = valueTimes.getOrDefault(val, 0) + 1;
            // 2. 更新valueTimes出现的次数
            valueTimes.put(val, valTimes);
            // 3.获取出现次数，所在的层节点
            ArrayList<Integer> arr = cntValues.getOrDefault(valTimes, new ArrayList<>());
            // 4.在该层的arr添加cal
            arr.add(val);
            // 5.更新层节点的map
            cntValues.put(valTimes, arr);
            // 6.更新次数最大频率值
            topicTimes = Math.max(topicTimes, valTimes);
        }

        /**
         * 删除并返回堆栈中出现频率最高的元素。<br/>
         * 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。(包含栈顶)
         *
         * @return
         */
        public int pop() {
            // 获取最大值，所在的层节点
            ArrayList<Integer> arr = cntValues.get(topicTimes);
            // 获取未节点（stack，后进先出）
            Integer ans = arr.remove(arr.size() - 1);
            // 移除
            if (arr.isEmpty()) {
                cntValues.remove(topicTimes--);
            }
            // ans所在的map，出现次数更新
            Integer values = valueTimes.get(ans);
            if (values == 1) {
                valueTimes.remove(ans);
            }else {
                valueTimes.put(ans, --values);
            }
            return ans;
        }
    }
}
